Aminet 40/Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso/Aminet/dev/lang/Python16_Src.lha/Python16_Source/Modules/regexpr.c

C/C++ Source or Header | 2000-09-10 | 45.9 KB | 2,137 lines

/* regexpr.c
 *
 * Author: Tatu Ylonen <[e-mail]>
 *
 * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose is hereby granted without
 * fee, provided that the above copyright notice appear in all copies.
 * This software is provided "as is" without express or implied
 * warranty.
 *
 * Created: Thu Sep 26 17:14:05 1991 ylo
 * Last modified: Mon Nov  4 17:06:48 1991 ylo
 * Ported to Think C: 19 Jan 1992 [e-mail]
 *
 * This code draws many ideas from the regular expression packages by
 * Henry Spencer of the University of Toronto and Richard Stallman of
 * the Free Software Foundation.
 *
 * Emacs-specific code and syntax table code is almost directly borrowed
 * from GNU regexp.
 *
 * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April
 * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim
 * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and
 * probably one or two others that I'm forgetting.
 *
 * $Id: regexpr.c,v 1.30 1999/04/10 15:46:56 guido Exp $ */

#include "Python.h"
#include "regexpr.h"
#include <assert.h>
#include "protos/regexpr.h"

/* The original code blithely assumed that sizeof(short) == 2.  Not
 * always true.  Original instances of "(short)x" were replaced by
 * SHORT(x), where SHORT is #defined below.  */

#define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x))

/* The stack implementation is taken from an idea by Andrew Kuchling.
 * It's a doubly linked list of arrays. The advantages of this over a
 * simple linked list are that the number of mallocs required are
 * reduced. It also makes it possible to statically allocate enough
 * space so that small patterns don't ever need to call malloc.
 *
 * The advantages over a single array is that is periodically
 * realloced when more space is needed is that we avoid ever copying
 * the stack. */

/* item_t is the basic stack element.  Defined as a union of
 * structures so that both registers, failure points, and counters can
 * be pushed/popped from the stack.  There's nothing built into the
 * item to keep track of whether a certain stack item is a register, a
 * failure point, or a counter. */

typedef union item_t
{
    struct
    {
        int num;
        int level;
        unsigned char *start;
        unsigned char *end;
    } reg;
    struct
    {
        int count;
        int level;
        int phantom;
        unsigned char *code;
        unsigned char *text;
    } fail;
    struct
    {
        int num;
        int level;
        int count;
    } cntr;
} item_t;

#define STACK_PAGE_SIZE 256
#define NUM_REGISTERS 256

/* A 'page' of stack items. */

typedef struct item_page_t
{
    item_t items[STACK_PAGE_SIZE];
    struct item_page_t *prev;
    struct item_page_t *next;
} item_page_t;


typedef struct match_state
{
    /* The number of registers that have been pushed onto the stack
     * since the last failure point. */

    int count;

    /* Used to control when registers need to be pushed onto the
     * stack. */

    int level;

    /* The number of failure points on the stack. */

    int point;

    /* Storage for the registers.  Each register consists of two
     * pointers to characters.  So register N is represented as
     * start[N] and end[N].  The pointers must be converted to
     * offsets from the beginning of the string before returning the
     * registers to the calling program. */

    unsigned char *start[NUM_REGISTERS];
    unsigned char *end[NUM_REGISTERS];

    /* Keeps track of whether a register has changed recently. */

    int changed[NUM_REGISTERS];

    /* Structure to encapsulate the stack. */
    struct
    {
        /* index into the curent page.  If index == 0 and you need
         * to pop an item, move to the previous page and set index
         * = STACK_PAGE_SIZE - 1.  Otherwise decrement index to
         * push a page. If index == STACK_PAGE_SIZE and you need
         * to push a page move to the next page and set index =
         * 0. If there is no new next page, allocate a new page
         * and link it in. Otherwise, increment index to push a
         * page. */

        int index;
        item_page_t *current; /* Pointer to the current page. */
        item_page_t first; /* First page is statically allocated. */
    } stack;
} match_state;

/* Initialize a state object */

/* #define NEW_STATE(state) \ */
/* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */
/* state.stack.current = &state.stack.first; \ */
/* state.stack.first.prev = NULL; \ */
/* state.stack.first.next = NULL; \ */
/* state.stack.index = 0; \ */
/* state.level = 1 */

#define NEW_STATE(state, nregs) \
{ \
    int i; \
    for (i = 0; i < nregs; i++) \
    { \
        state.start[i] = NULL; \
        state.end[i] = NULL; \
        state.changed[i] = 0; \
    } \
    state.stack.current = &state.stack.first; \
    state.stack.first.prev = NULL; \
    state.stack.first.next = NULL; \
    state.stack.index = 0; \
    state.level = 1; \
    state.count = 0; \
    state.level = 0; \
    state.point = 0; \
}

/* Free any memory that might have been malloc'd */

#define FREE_STATE(state) \
while(state.stack.first.next != NULL) \
{ \
    state.stack.current = state.stack.first.next; \
    state.stack.first.next = state.stack.current->next; \
    free(state.stack.current); \
}

/* Discard the top 'count' stack items. */

#define STACK_DISCARD(stack, count, on_error) \
stack.index -= count; \
while (stack.index < 0) \
{ \
    if (stack.current->prev == NULL) \
        on_error; \
    stack.current = stack.current->prev; \
    stack.index += STACK_PAGE_SIZE; \
}

/* Store a pointer to the previous item on the stack. Used to pop an
 * item off of the stack. */

#define STACK_PREV(stack, top, on_error) \
if (stack.index == 0) \
{ \
    if (stack.current->prev == NULL) \
        on_error; \
    stack.current = stack.current->prev; \
    stack.index = STACK_PAGE_SIZE - 1; \
} \
else \
{ \
    stack.index--; \
} \
top = &(stack.current->items[stack.index])

/* Store a pointer to the next item on the stack. Used to push an item
 * on to the stack. */

#define STACK_NEXT(stack, top, on_error) \
if (stack.index == STACK_PAGE_SIZE) \
{ \
    if (stack.current->next == NULL) \
    { \
        stack.current->next = (item_page_t *)malloc(sizeof(item_page_t)); \
        if (stack.current->next == NULL) \
            on_error; \
        stack.current->next->prev = stack.current; \
        stack.current->next->next = NULL; \
    } \
    stack.current = stack.current->next; \
    stack.index = 0; \
} \
top = &(stack.current->items[stack.index++])

/* Store a pointer to the item that is 'count' items back in the
 * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to
 * STACK_TOP(stack, top, on_error).  */

#define STACK_BACK(stack, top, count, on_error) \
{ \
    int index; \
    item_page_t *current; \
    current = stack.current; \
    index = stack.index - (count); \
    while (index < 0) \
    { \
        if (current->prev == NULL) \
            on_error; \
        current = current->prev; \
        index += STACK_PAGE_SIZE; \
    } \
    top = &(current->items[index]); \
}

/* Store a pointer to the top item on the stack. Execute the
 * 'on_error' code if there are no items on the stack. */

#define STACK_TOP(stack, top, on_error) \
if (stack.index == 0) \
{ \
    if (stack.current->prev == NULL) \
        on_error; \
    top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
} \
else \
{ \
    top = &(stack.current->items[stack.index - 1]); \
}

/* Test to see if the stack is empty */

#define STACK_EMPTY(stack) ((stack.index == 0) && \
                (stack.current->prev == NULL))

/* Return the start of register 'reg' */

#define GET_REG_START(state, reg) (state.start[reg])

/* Return the end of register 'reg' */

#define GET_REG_END(state, reg) (state.end[reg])

/* Set the start of register 'reg'. If the state of the register needs
 * saving, push it on the stack. */

#define SET_REG_START(state, reg, text, on_error) \
if(state.changed[reg] < state.level) \
{ \
    item_t *item; \
    STACK_NEXT(state.stack, item, on_error); \
    item->reg.num = reg; \
    item->reg.start = state.start[reg]; \
    item->reg.end = state.end[reg]; \
    item->reg.level = state.changed[reg]; \
    state.changed[reg] = state.level; \
    state.count++; \
} \
state.start[reg] = text

/* Set the end of register 'reg'. If the state of the register needs
 * saving, push it on the stack. */

#define SET_REG_END(state, reg, text, on_error) \
if(state.changed[reg] < state.level) \
{ \
    item_t *item; \
    STACK_NEXT(state.stack, item, on_error); \
    item->reg.num = reg; \
    item->reg.start = state.start[reg]; \
    item->reg.end = state.end[reg]; \
    item->reg.level = state.changed[reg]; \
    state.changed[reg] = state.level; \
    state.count++; \
} \
state.end[reg] = text

#define PUSH_FAILURE(state, xcode, xtext, on_error) \
{ \
    item_t *item; \
    STACK_NEXT(state.stack, item, on_error); \
    item->fail.code = xcode; \
    item->fail.text = xtext; \
    item->fail.count = state.count; \
    item->fail.level = state.level; \
    item->fail.phantom = 0; \
    state.count = 0; \
    state.level++; \
    state.point++; \
}

/* Update the last failure point with a new position in the text. */

#define UPDATE_FAILURE(state, xtext, on_error) \
{ \
    item_t *item; \
    STACK_BACK(state.stack, item, state.count + 1, on_error); \
    if (!item->fail.phantom) \
    { \
        item_t *item2; \
        STACK_NEXT(state.stack, item2, on_error); \
        item2->fail.code = item->fail.code; \
        item2->fail.text = xtext; \
        item2->fail.count = state.count; \
        item2->fail.level = state.level; \
        item2->fail.phantom = 1; \
        state.count = 0; \
        state.level++; \
        state.point++; \
    } \
    else \
    { \
        STACK_DISCARD(state.stack, state.count, on_error); \
        STACK_TOP(state.stack, item, on_error); \
        item->fail.text = xtext; \
        state.count = 0; \
        state.level++; \
    } \
}

#define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \
{ \
    item_t *item; \
    do \
    { \
        while(state.count > 0) \
        { \
            STACK_PREV(state.stack, item, on_error); \
            state.start[item->reg.num] = item->reg.start; \
            state.end[item->reg.num] = item->reg.end; \
            state.changed[item->reg.num] = item->reg.level; \
            state.count--; \
        } \
        STACK_PREV(state.stack, item, on_empty); \
        xcode = item->fail.code; \
        xtext = item->fail.text; \
        state.count = item->fail.count; \
        state.level = item->fail.level; \
        state.point--; \
    } \
    while (item->fail.text == NULL); \
}

enum regexp_compiled_ops /* opcodes for compiled regexp */
{
    Cend,              /* end of pattern reached */
    Cbol,              /* beginning of line */
    Ceol,              /* end of line */
    Cset,              /* character set.  Followed by 32 bytes of set. */
    Cexact,              /* followed by a byte to match */
    Canychar,          /* matches any character except newline */
    Cstart_memory,          /* set register start addr (followed by reg number) */
    Cend_memory,          /* set register end addr (followed by reg number) */
    Cmatch_memory,          /* match a duplicate of reg contents (regnum follows)*/
    Cjump,              /* followed by two bytes (lsb,msb) of displacement. */
    Cstar_jump,          /* will change to jump/update_failure_jump at runtime */
    Cfailure_jump,          /* jump to addr on failure */
    Cupdate_failure_jump, /* update topmost failure point and jump */
    Cdummy_failure_jump,  /* push a dummy failure point and jump */
    Cbegbuf,          /* match at beginning of buffer */
    Cendbuf,          /* match at end of buffer */
    Cwordbeg,          /* match at beginning of word */
    Cwordend,          /* match at end of word */
    Cwordbound,          /* match if at word boundary */
    Cnotwordbound,        /* match if not at word boundary */
    Csyntaxspec,          /* matches syntax code (1 byte follows) */
    Cnotsyntaxspec,       /* matches if syntax code does not match (1 byte follows) */
    Crepeat1
};

enum regexp_syntax_op    /* syntax codes for plain and quoted characters */
{
    Rend,          /* special code for end of regexp */
    Rnormal,      /* normal character */
    Ranychar,      /* any character except newline */
    Rquote,          /* the quote character */
    Rbol,          /* match beginning of line */
    Reol,          /* match end of line */
    Roptional,      /* match preceding expression optionally */
    Rstar,          /* match preceding expr zero or more times */
    Rplus,          /* match preceding expr one or more times */
    Ror,          /* match either of alternatives */
    Ropenpar,      /* opening parenthesis */
    Rclosepar,      /* closing parenthesis */
    Rmemory,      /* match memory register */
    Rextended_memory, /* \vnn to match registers 10-99 */
    Ropenset,      /* open set.  Internal syntax hard-coded below. */
    /* the following are gnu extensions to "normal" regexp syntax */
    Rbegbuf,      /* beginning of buffer */
    Rendbuf,      /* end of buffer */
    Rwordchar,      /* word character */
    Rnotwordchar,      /* not word character */
    Rwordbeg,      /* beginning of word */
    Rwordend,      /* end of word */
    Rwordbound,      /* word bound */
    Rnotwordbound,      /* not word bound */
    Rnum_ops
};

static int re_compile_initialized = 0;
static int regexp_syntax = 0;
int re_syntax = 0; /* Exported copy of regexp_syntax */
static unsigned char regexp_plain_ops[256];
static unsigned char regexp_quoted_ops[256];
static unsigned char regexp_precedences[Rnum_ops];
static int regexp_context_indep_ops;
static int regexp_ansi_sequences;

#define NUM_LEVELS  5    /* number of precedence levels in use */
#define MAX_NESTING 100  /* max nesting level of operators */

#define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]

unsigned char re_syntax_table[256];

void re_compile_initialize()
{
    int a;

    static int syntax_table_inited = 0;

    if (!syntax_table_inited)
    {
        syntax_table_inited = 1;
        memset(re_syntax_table, 0, 256);
        for (a = 'a'; a <= 'z'; a++)
            re_syntax_table[a] = Sword;
        for (a = 'A'; a <= 'Z'; a++)
            re_syntax_table[a] = Sword;
        for (a = '0'; a <= '9'; a++)
            re_syntax_table[a] = Sword | Sdigit | Shexdigit;
        for (a = '0'; a <= '7'; a++)
            re_syntax_table[a] |= Soctaldigit;
        for (a = 'A'; a <= 'F'; a++)
            re_syntax_table[a] |= Shexdigit;
        for (a = 'a'; a <= 'f'; a++)
            re_syntax_table[a] |= Shexdigit;
        re_syntax_table['_'] = Sword;
        for (a = 9; a <= 13; a++)
            re_syntax_table[a] = Swhitespace;
        re_syntax_table[' '] = Swhitespace;
    }
    re_compile_initialized = 1;
    for (a = 0; a < 256; a++)
    {
        regexp_plain_ops[a] = Rnormal;
        regexp_quoted_ops[a] = Rnormal;
    }
    for (a = '0'; a <= '9'; a++)
        regexp_quoted_ops[a] = Rmemory;
    regexp_plain_ops['\134'] = Rquote;
    if (regexp_syntax & RE_NO_BK_PARENS)
    {
        regexp_plain_ops['('] = Ropenpar;
        regexp_plain_ops[')'] = Rclosepar;
    }
    else
    {
        regexp_quoted_ops['('] = Ropenpar;
        regexp_quoted_ops[')'] = Rclosepar;
    }
    if (regexp_syntax & RE_NO_BK_VBAR)
        regexp_plain_ops['\174'] = Ror;
    else
        regexp_quoted_ops['\174'] = Ror;
    regexp_plain_ops['*'] = Rstar;
    if (regexp_syntax & RE_BK_PLUS_QM)
    {
        regexp_quoted_ops['+'] = Rplus;
        regexp_quoted_ops['?'] = Roptional;
    }
    else
    {
        regexp_plain_ops['+'] = Rplus;
        regexp_plain_ops['?'] = Roptional;
    }
    if (regexp_syntax & RE_NEWLINE_OR)
        regexp_plain_ops['\n'] = Ror;
    regexp_plain_ops['\133'] = Ropenset;
    regexp_plain_ops['\136'] = Rbol;
    regexp_plain_ops['$'] = Reol;
    regexp_plain_ops['.'] = Ranychar;
    if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
    {
        regexp_quoted_ops['w'] = Rwordchar;
        regexp_quoted_ops['W'] = Rnotwordchar;
        regexp_quoted_ops['<'] = Rwordbeg;
        regexp_quoted_ops['>'] = Rwordend;
        regexp_quoted_ops['b'] = Rwordbound;
        regexp_quoted_ops['B'] = Rnotwordbound;
        regexp_quoted_ops['`'] = Rbegbuf;
        regexp_quoted_ops['\''] = Rendbuf;
    }
    if (regexp_syntax & RE_ANSI_HEX)
        regexp_quoted_ops['v'] = Rextended_memory;
    for (a = 0; a < Rnum_ops; a++)
        regexp_precedences[a] = 4;
    if (regexp_syntax & RE_TIGHT_VBAR)
    {
        regexp_precedences[Ror] = 3;
        regexp_precedences[Rbol] = 2;
        regexp_precedences[Reol] = 2;
    }
    else
    {
        regexp_precedences[Ror] = 2;
        regexp_precedences[Rbol] = 3;
        regexp_precedences[Reol] = 3;
    }
    regexp_precedences[Rclosepar] = 1;
    regexp_precedences[Rend] = 0;
    regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
    regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
}

int re_set_syntax(syntax)
    int syntax;
{
    int ret;

    ret = regexp_syntax;
    regexp_syntax = syntax;
    re_syntax = syntax; /* Exported copy */
    re_compile_initialize();
    return ret;
}

static int hex_char_to_decimal(ch)
    int ch;
{
    if (ch >= '0' && ch <= '9')
        return ch - '0';
    if (ch >= 'a' && ch <= 'f')
        return ch - 'a' + 10;
    if (ch >= 'A' && ch <= 'F')
        return ch - 'A' + 10;
    return 16;
}

static void re_compile_fastmap_aux(code,
                   pos,
                   visited,
                   can_be_null,
                   fastmap)
    unsigned char *code;
    int pos;
    unsigned char *visited;
    unsigned char *can_be_null;
    unsigned char *fastmap;
{
    int a;
    int b;
    int syntaxcode;

    if (visited[pos])
        return;  /* we have already been here */
    visited[pos] = 1;
    for (;;)
        switch (code[pos++]) {
        case Cend:
            {
                *can_be_null = 1;
                return;
            }
        case Cbol:
        case Cbegbuf:
        case Cendbuf:
        case Cwordbeg:
        case Cwordend:
        case Cwordbound:
        case Cnotwordbound:
        {
            for (a = 0; a < 256; a++)
                fastmap[a] = 1;
            break;
        }
        case Csyntaxspec:
        {
            syntaxcode = code[pos++];
            for (a = 0; a < 256; a++)
                if (SYNTAX(a) & syntaxcode)
                    fastmap[a] = 1;
            return;
        }
        case Cnotsyntaxspec:
        {
            syntaxcode = code[pos++];
            for (a = 0; a < 256; a++)
                if (!(SYNTAX(a) & syntaxcode) )
                    fastmap[a] = 1;
            return;
        }
        case Ceol:
        {
            fastmap['\n'] = 1;
            if (*can_be_null == 0)
                *can_be_null = 2; /* can match null, but only at end of buffer*/
            return;
        }
        case Cset:
        {
            for (a = 0; a < 256/8; a++)
                if (code[pos + a] != 0)
                    for (b = 0; b < 8; b++)
                        if (code[pos + a] & (1 << b))
                            fastmap[(a << 3) + b] = 1;
            pos += 256/8;
            return;
        }
        case Cexact:
        {
            fastmap[(unsigned char)code[pos]] = 1;
            return;
        }
        case Canychar:
        {
            for (a = 0; a < 256; a++)
                if (a != '\n')
                    fastmap[a] = 1;
            return;
        }
        case Cstart_memory:
        case Cend_memory:
        {
            pos++;
            break;
        }
        case Cmatch_memory:
        {
            for (a = 0; a < 256; a++)
                fastmap[a] = 1;
            *can_be_null = 1;
            return;
        }
        case Cjump:
        case Cdummy_failure_jump:
        case Cupdate_failure_jump:
        case Cstar_jump:
        {
            a = (unsigned char)code[pos++];
            a |= (unsigned char)code[pos++] << 8;
            pos += (int)SHORT(a);
            if (visited[pos])
            {
                /* argh... the regexp contains empty loops.  This is not
                   good, as this may cause a failure stack overflow when
                   matching.  Oh well. */
                /* this path leads nowhere; pursue other paths. */
                return;
            }
            visited[pos] = 1;
            break;
        }
        case Cfailure_jump:
        {
            a = (unsigned char)code[pos++];
            a |= (unsigned char)code[pos++] << 8;
            a = pos + (int)SHORT(a);
            re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap);
            break;
        }
        case Crepeat1:
        {
            pos += 2;
            break;
        }
        default:
        {
                PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
                return;
            /*NOTREACHED*/
        }
        }
}

static int re_do_compile_fastmap(buffer,
                 used,
                 pos,
                 can_be_null,
                 fastmap)
    unsigned char *buffer;
    int used;
    int pos;
    unsigned char *can_be_null;
    unsigned char *fastmap;
{
    unsigned char small_visited[512], *visited;

    if (used <= sizeof(small_visited))
        visited = small_visited;
    else
    {
        visited = malloc(used);
        if (!visited)
            return 0;
    }
    *can_be_null = 0;
    memset(fastmap, 0, 256);
    memset(visited, 0, used);
    re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap);
    if (visited != small_visited)
        free(visited);
    return 1;
}

void re_compile_fastmap(bufp)
    regexp_t bufp;
{
    if (!bufp->fastmap || bufp->fastmap_accurate)
        return;
    assert(bufp->used > 0);
    if (!re_do_compile_fastmap(bufp->buffer,
                   bufp->used,
                   0,
                   &bufp->can_be_null,
                   bufp->fastmap))
        return;
    if (PyErr_Occurred()) return;
    if (bufp->buffer[0] == Cbol)
        bufp->anchor = 1;   /* begline */
    else
        if (bufp->buffer[0] == Cbegbuf)
            bufp->anchor = 2; /* begbuf */
        else
            bufp->anchor = 0; /* none */
    bufp->fastmap_accurate = 1;
}

/*
 * star is coded as:
 * 1: failure_jump 2
 *    ... code for operand of star
 *    star_jump 1
 * 2: ... code after star
 *
 * We change the star_jump to update_failure_jump if we can determine
 * that it is safe to do so; otherwise we change it to an ordinary
 * jump.
 *
 * plus is coded as
 *
 *    jump 2
 * 1: failure_jump 3
 * 2: ... code for operand of plus
 *    star_jump 1
 * 3: ... code after plus
 *
 * For star_jump considerations this is processed identically to star.
 *
 */

static int re_optimize_star_jump(bufp, code)
    regexp_t bufp;
    unsigned char *code;
{
    unsigned char map[256];
    unsigned char can_be_null;
    unsigned char *p1;
    unsigned char *p2;
    unsigned char ch;
    int a;
    int b;
    int num_instructions = 0;

    a = (unsigned char)*code++;
    a |= (unsigned char)*code++ << 8;
    a = (int)SHORT(a);

    p1 = code + a + 3; /* skip the failure_jump */
    /* Check that the jump is within the pattern */
    if (p1<bufp->buffer || bufp->buffer+bufp->used<p1)
      {
        PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (failure_jump opt)");
        return 0;
      }

    assert(p1[-3] == Cfailure_jump);
    p2 = code;
    /* p1 points inside loop, p2 points to after loop */
    if (!re_do_compile_fastmap(bufp->buffer, bufp->used,
                   (int)(p2 - bufp->buffer),
                   &can_be_null, map))
        goto make_normal_jump;

    /* If we might introduce a new update point inside the
     * loop, we can't optimize because then update_jump would
     * update a wrong failure point.  Thus we have to be
     * quite careful here.
     */

    /* loop until we find something that consumes a character */
  loop_p1:
    num_instructions++;
    switch (*p1++)
    {
    case Cbol:
    case Ceol:
    case Cbegbuf:
    case Cendbuf:
    case Cwordbeg:
    case Cwordend:
    case Cwordbound:
    case Cnotwordbound:
    {
        goto loop_p1;
    }
    case Cstart_memory:
    case Cend_memory:
    {
        p1++;
        goto loop_p1;
    }
    case Cexact:
    {
        ch = (unsigned char)*p1++;
        if (map[(int)ch])
            goto make_normal_jump;
        break;
    }
    case Canychar:
    {
        for (b = 0; b < 256; b++)
            if (b != '\n' && map[b])
                goto make_normal_jump;
        break;
    }
    case Cset:
    {
        for (b = 0; b < 256; b++)
            if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
                goto make_normal_jump;
        p1 += 256/8;
        break;
    }
    default:
    {
        goto make_normal_jump;
    }
    }
    /* now we know that we can't backtrack. */
    while (p1 != p2 - 3)
    {
        num_instructions++;
        switch (*p1++)
        {
        case Cend:
        {
            return 0;
        }
        case Cbol:
        case Ceol:
        case Canychar:
        case Cbegbuf:
        case Cendbuf:
        case Cwordbeg:
        case Cwordend:
        case Cwordbound:
        case Cnotwordbound:
        {
            break;
        }
        case Cset:
        {
            p1 += 256/8;
            break;
        }
        case Cexact:
        case Cstart_memory:
        case Cend_memory:
        case Cmatch_memory:
        case Csyntaxspec:
        case Cnotsyntaxspec:
        {
            p1++;
            break;
        }
        case Cjump:
        case Cstar_jump:
        case Cfailure_jump:
        case Cupdate_failure_jump:
        case Cdummy_failure_jump:
        {
            goto make_normal_jump;
        }
        default:
        {
            return 0;
        }
        }
    }

    /* make_update_jump: */
    code -= 3;
    a += 3;  /* jump to after the Cfailure_jump */
    code[0] = Cupdate_failure_jump;
    code[1] = a & 0xff;
    code[2] = a >> 8;
    if (num_instructions > 1)
        return 1;
    assert(num_instructions == 1);
    /* if the only instruction matches a single character, we can do
     * better */
    p1 = code + 3 + a;   /* start of sole instruction */
    if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
        *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
        code[0] = Crepeat1;
    return 1;

  make_normal_jump:
    code -= 3;
    *code = Cjump;
    return 1;
}

static int re_optimize(bufp)
    regexp_t bufp;
{
    unsigned char *code;

    code = bufp->buffer;

    while(1)
    {
        switch (*code++)
        {
        case Cend:
        {
            return 1;
        }
        case Canychar:
        case Cbol:
        case Ceol:
        case Cbegbuf:
        case Cendbuf:
        case Cwordbeg:
        case Cwordend:
        case Cwordbound:
        case Cnotwordbound:
        {
            break;
        }
        case Cset:
        {
            code += 256/8;
            break;
        }
        case Cexact:
        case Cstart_memory:
        case Cend_memory:
        case Cmatch_memory:
        case Csyntaxspec:
        case Cnotsyntaxspec:
        {
            code++;
            break;
        }
        case Cstar_jump:
        {
            if (!re_optimize_star_jump(bufp, code))
            {
                return 0;
            }
            /* fall through */
        }
        case Cupdate_failure_jump:
        case Cjump:
        case Cdummy_failure_jump:
        case Cfailure_jump:
        case Crepeat1:
        {
            code += 2;
            break;
        }
        default:
        {
            return 0;
        }
        }
    }
}

#define NEXTCHAR(var) \
{ \
    if (pos >= size) \
        goto ends_prematurely; \
    (var) = regex[pos]; \
    pos++; \
}

#define ALLOC(amount) \
{ \
      if (pattern_offset+(amount) > alloc) \
      { \
          alloc += 256 + (amount); \
          pattern = realloc(pattern, alloc); \
          if (!pattern) \
              goto out_of_memory; \
      } \
}

#define STORE(ch) pattern[pattern_offset++] = (ch)

#define CURRENT_LEVEL_START (starts[starts_base + current_level])

#define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset

#define PUSH_LEVEL_STARTS \
if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
    starts_base += NUM_LEVELS; \
else \
    goto too_complex \

#define POP_LEVEL_STARTS starts_base -= NUM_LEVELS

#define PUT_ADDR(offset,addr) \
{ \
    int disp = (addr) - (offset) - 2; \
    pattern[(offset)] = disp & 0xff; \
    pattern[(offset)+1] = (disp>>8) & 0xff; \
}

#define INSERT_JUMP(pos,type,addr) \
{ \
    int a, p = (pos), t = (type), ad = (addr); \
    for (a = pattern_offset - 1; a >= p; a--) \
        pattern[a + 3] = pattern[a]; \
    pattern[p] = t; \
    PUT_ADDR(p+1,ad); \
    pattern_offset += 3; \
}

#define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))

#define SET_FIELDS \
{ \
    bufp->allocated = alloc; \
    bufp->buffer = pattern; \
    bufp->used = pattern_offset; \
}

#define GETHEX(var) \
{ \
    unsigned char gethex_ch, gethex_value; \
    NEXTCHAR(gethex_ch); \
    gethex_value = hex_char_to_decimal(gethex_ch); \
    if (gethex_value == 16) \
        goto hex_error; \
    NEXTCHAR(gethex_ch); \
    gethex_ch = hex_char_to_decimal(gethex_ch); \
    if (gethex_ch == 16) \
        goto hex_error; \
    (var) = gethex_value * 16 + gethex_ch; \
}

#define ANSI_TRANSLATE(ch) \
{ \
    switch (ch) \
    { \
    case 'a': \
    case 'A': \
    { \
        ch = 7; /* audible bell */ \
        break; \
    } \
    case 'b': \
    case 'B': \
    { \
        ch = 8; /* backspace */ \
        break; \
    } \
    case 'f': \
    case 'F': \
    { \
        ch = 12; /* form feed */ \
        break; \
    } \
    case 'n': \
    case 'N': \
    { \
        ch = 10; /* line feed */ \
        break; \
    } \
    case 'r': \
    case 'R': \
    { \
        ch = 13; /* carriage return */ \
        break; \
    } \
    case 't': \
    case 'T': \
    { \
          ch = 9; /* tab */ \
          break; \
    } \
    case 'v': \
    case 'V': \
    { \
        ch = 11; /* vertical tab */ \
        break; \
    } \
    case 'x': /* hex code */ \
    case 'X': \
    { \
        GETHEX(ch); \
        break; \
    } \
    default: \
    { \
        /* other characters passed through */ \
        if (translate) \
            ch = translate[(unsigned char)ch]; \
        break; \
    } \
    } \
}

char *re_compile_pattern(regex, size, bufp)
    unsigned char *regex;
    int size;
    regexp_t bufp;
{
    int a;
    int pos;
    int op;
    int current_level;
    int level;
    int opcode;
    int pattern_offset = 0, alloc;
    int starts[NUM_LEVELS * MAX_NESTING];
    int starts_base;
    int future_jumps[MAX_NESTING];
    int num_jumps;
    unsigned char ch = '\0';
    unsigned char *pattern;
    unsigned char *translate;
    int next_register;
    int paren_depth;
    int num_open_registers;
    int open_registers[RE_NREGS];
    int beginning_context;

    if (!re_compile_initialized)
        re_compile_initialize();
    bufp->used = 0;
    bufp->fastmap_accurate = 0;
    bufp->uses_registers = 1;
    bufp->num_registers = 1;
    translate = bufp->translate;
    pattern = bufp->buffer;
    alloc = bufp->allocated;
    if (alloc == 0 || pattern == NULL)
    {
        alloc = 256;
        pattern = malloc(alloc);
        if (!pattern)
            goto out_of_memory;
    }
    pattern_offset = 0;
    starts_base = 0;
    num_jumps = 0;
    current_level = 0;
    SET_LEVEL_START;
    num_open_registers = 0;
    next_register = 1;
    paren_depth = 0;
    beginning_context = 1;
    op = -1;
    /* we use Rend dummy to ensure that pending jumps are updated
       (due to low priority of Rend) before exiting the loop. */
    pos = 0;
    while (op != Rend)
    {
        if (pos >= size)
            op = Rend;
        else
        {
            NEXTCHAR(ch);
            if (translate)
                ch = translate[(unsigned char)ch];
            op = regexp_plain_ops[(unsigned char)ch];
            if (op == Rquote)
            {
                NEXTCHAR(ch);
                op = regexp_quoted_ops[(unsigned char)ch];
                if (op == Rnormal && regexp_ansi_sequences)
                    ANSI_TRANSLATE(ch);
            }
        }
        level = regexp_precedences[op];
        /* printf("ch='%c' op=%d level=%d current_level=%d
           curlevstart=%d\n", ch, op, level, current_level,
           CURRENT_LEVEL_START); */
        if (level > current_level)
        {
            for (current_level++; current_level < level; current_level++)
                SET_LEVEL_START;
            SET_LEVEL_START;
        }
        else
            if (level < current_level)
            {
                current_level = level;
                for (;num_jumps > 0 &&
                         future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
                     num_jumps--)
                    PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
            }
        switch (op)
        {
        case Rend:
        {
            break;
        }
        case Rnormal:
        {
          normal_char:
            opcode = Cexact;
          store_opcode_and_arg: /* opcode & ch must be set */
            SET_LEVEL_START;
            ALLOC(2);
            STORE(opcode);
            STORE(ch);
            break;
        }
        case Ranychar:
        {
            opcode = Canychar;
          store_opcode:
            SET_LEVEL_START;
            ALLOC(1);
            STORE(opcode);
            break;
        }
        case Rquote:
        {
            abort();
            /*NOTREACHED*/
        }
        case Rbol:
        {
            if (!beginning_context) {
                if (regexp_context_indep_ops)
                    goto op_error;
                else
                    goto normal_char;
            }
            opcode = Cbol;
            goto store_opcode;
        }
        case Reol:
        {
            if (!((pos >= size) ||
                  ((regexp_syntax & RE_NO_BK_VBAR) ?
                   (regex[pos] == '\174') :
                   (pos+1 < size && regex[pos] == '\134' &&
                regex[pos+1] == '\174')) ||
                  ((regexp_syntax & RE_NO_BK_PARENS)?
                   (regex[pos] == ')'):
                   (pos+1 < size && regex[pos] == '\134' &&
                regex[pos+1] == ')')))) {
                if (regexp_context_indep_ops)
                    goto op_error;
                else
                    goto normal_char;
            }
            opcode = Ceol;
            goto store_opcode;
            /* NOTREACHED */
            break;
        }
        case Roptional:
        {
            if (beginning_context) {
                if (regexp_context_indep_ops)
                    goto op_error;
                else
                    goto normal_char;
            }
            if (CURRENT_LEVEL_START == pattern_offset)
                break; /* ignore empty patterns for ? */
            ALLOC(3);
            INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
                    pattern_offset + 3);
            break;
        }
        case Rstar:
        case Rplus:
        {
            if (beginning_context) {
                if (regexp_context_indep_ops)
                    goto op_error;
                else
                    goto normal_char;
            }
            if (CURRENT_LEVEL_START == pattern_offset)
                break; /* ignore empty patterns for + and * */
            ALLOC(9);
            INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
                    pattern_offset + 6);
            INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
            if (op == Rplus)  /* jump over initial failure_jump */
                INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
                        CURRENT_LEVEL_START + 6);
            break;
        }
        case Ror:
        {
            ALLOC(6);
            INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
                    pattern_offset + 6);
            if (num_jumps >= MAX_NESTING)
                goto too_complex;
            STORE(Cjump);
            future_jumps[num_jumps++] = pattern_offset;
            STORE(0);
            STORE(0);
            SET_LEVEL_START;
            break;
        }
        case Ropenpar:
        {
            SET_LEVEL_START;
            if (next_register < RE_NREGS)
            {
                bufp->uses_registers = 1;
                ALLOC(2);
                STORE(Cstart_memory);
                STORE(next_register);
                open_registers[num_open_registers++] = next_register;
                bufp->num_registers++;
                next_register++;
            }
            paren_depth++;
            PUSH_LEVEL_STARTS;
            current_level = 0;
            SET_LEVEL_START;
            break;
        }
        case Rclosepar:
        {
            if (paren_depth <= 0)
                goto parenthesis_error;
            POP_LEVEL_STARTS;
            current_level = regexp_precedences[Ropenpar];
            paren_depth--;
            if (paren_depth < num_open_registers)
            {
                bufp->uses_registers = 1;
                ALLOC(2);
                STORE(Cend_memory);
                num_open_registers--;
                STORE(open_registers[num_open_registers]);
            }
            break;
        }
        case Rmemory:
        {
            if (ch == '0')
                goto bad_match_register;
            assert(ch >= '0' && ch <= '9');
            bufp->uses_registers = 1;
            opcode = Cmatch_memory;
            ch -= '0';
            goto store_opcode_and_arg;
        }
        case Rextended_memory:
        {
            NEXTCHAR(ch);
            if (ch < '0' || ch > '9')
                goto bad_match_register;
            NEXTCHAR(a);
            if (a < '0' || a > '9')
                goto bad_match_register;
            ch = 10 * (a - '0') + ch - '0';
            if (ch <= 0 || ch >= RE_NREGS)
                goto bad_match_register;
            bufp->uses_registers = 1;
            opcode = Cmatch_memory;
            goto store_opcode_and_arg;
        }
        case Ropenset:
        {
            int complement;
            int prev;
            int offset;
            int range;
            int firstchar;

            SET_LEVEL_START;
            ALLOC(1+256/8);
            STORE(Cset);
            offset = pattern_offset;
            for (a = 0; a < 256/8; a++)
                STORE(0);
            NEXTCHAR(ch);
            if (translate)
                ch = translate[(unsigned char)ch];
            if (ch == '\136')
            {
                complement = 1;
                NEXTCHAR(ch);
                if (translate)
                    ch = translate[(unsigned char)ch];
            }
            else
                complement = 0;
            prev = -1;
            range = 0;
            firstchar = 1;
            while (ch != '\135' || firstchar)
            {
                firstchar = 0;
                if (regexp_ansi_sequences && ch == '\134')
                {
                    NEXTCHAR(ch);
                    ANSI_TRANSLATE(ch);
                }
                if (range)
                {
                    for (a = prev; a <= (int)ch; a++)
                        SETBIT(pattern, offset, a);
                    prev = -1;
                    range = 0;
                }
                else
                    if (prev != -1 && ch == '-')
                        range = 1;
                    else
                    {
                        SETBIT(pattern, offset, ch);
                        prev = ch;
                    }
                NEXTCHAR(ch);
                if (translate)
                    ch = translate[(unsigned char)ch];
            }
            if (range)
                SETBIT(pattern, offset, '-');
            if (complement)
            {
                for (a = 0; a < 256/8; a++)
                    pattern[offset+a] ^= 0xff;
            }
            break;
        }
        case Rbegbuf:
        {
            opcode = Cbegbuf;
            goto store_opcode;
        }
        case Rendbuf:
        {
            opcode = Cendbuf;
            goto store_opcode;
        }
        case Rwordchar:
        {
            opcode = Csyntaxspec;
            ch = Sword;
            goto store_opcode_and_arg;
        }
        case Rnotwordchar:
        {
            opcode = Cnotsyntaxspec;
            ch = Sword;
            goto store_opcode_and_arg;
        }
        case Rwordbeg:
        {
            opcode = Cwordbeg;
            goto store_opcode;
        }
        case Rwordend:
        {
            opcode = Cwordend;
            goto store_opcode;
        }
        case Rwordbound:
        {
            opcode = Cwordbound;
            goto store_opcode;
        }
        case Rnotwordbound:
        {
            opcode = Cnotwordbound;
            goto store_opcode;
        }
        default:
        {
            abort();
        }
        }
        beginning_context = (op == Ropenpar || op == Ror);
    }
    if (starts_base != 0)
        goto parenthesis_error;
    assert(num_jumps == 0);
    ALLOC(1);
    STORE(Cend);
    SET_FIELDS;
    if(!re_optimize(bufp))
        return "Optimization error";
    return NULL;

  op_error:
    SET_FIELDS;
    return "Badly placed special character";

  bad_match_register:
    SET_FIELDS;
    return "Bad match register number";

  hex_error:
    SET_FIELDS;
    return "Bad hexadecimal number";

  parenthesis_error:
    SET_FIELDS;
    return "Badly placed parenthesis";

  out_of_memory:
    SET_FIELDS;
    return "Out of memory";

  ends_prematurely:
    SET_FIELDS;
    return "Regular expression ends prematurely";

  too_complex:
    SET_FIELDS;
    return "Regular expression too complex";
}

#undef CHARAT
#undef NEXTCHAR
#undef GETHEX
#undef ALLOC
#undef STORE
#undef CURRENT_LEVEL_START
#undef SET_LEVEL_START
#undef PUSH_LEVEL_STARTS
#undef POP_LEVEL_STARTS
#undef PUT_ADDR
#undef INSERT_JUMP
#undef SETBIT
#undef SET_FIELDS

#define PREFETCH if (text == textend) goto fail

#define NEXTCHAR(var) \
PREFETCH; \
var = (unsigned char)*text++; \
if (translate) \
    var = translate[var]

int re_match(bufp,
         string,
         size,
         pos,
         old_regs)
    regexp_t bufp;
    unsigned char *string;
    int size;
    int pos;
    regexp_registers_t old_regs;
{
    unsigned char *code;
    unsigned char *translate;
    unsigned char *text;
    unsigned char *textstart;
    unsigned char *textend;
    int a;
    int b;
    int ch;
    int reg;
    int match_end;
    unsigned char *regstart;
    unsigned char *regend;
    int regsize;
    match_state state;

    assert(pos >= 0 && size >= 0);
    assert(pos <= size);

    text = string + pos;
    textstart = string;
    textend = string + size;

    code = bufp->buffer;

    translate = bufp->translate;

    NEW_STATE(state, bufp->num_registers);

  continue_matching:
    switch (*code++)
    {
    case Cend:
    {
        match_end = text - textstart;
        if (old_regs)
        {
            old_regs->start[0] = pos;
            old_regs->end[0] = match_end;
            if (!bufp->uses_registers)
            {
                for (a = 1; a < RE_NREGS; a++)
                {
                    old_regs->start[a] = -1;
                    old_regs->end[a] = -1;
                }
            }
            else
            {
                for (a = 1; a < bufp->num_registers; a++)
                {
                    if ((GET_REG_START(state, a) == NULL) ||
                        (GET_REG_END(state, a) == NULL))
                    {
                        old_regs->start[a] = -1;
                        old_regs->end[a] = -1;
                        continue;
                    }
                    old_regs->start[a] = GET_REG_START(state, a) - textstart;
                    old_regs->end[a] = GET_REG_END(state, a) - textstart;
                }
                for (; a < RE_NREGS; a++)
                {
                    old_regs->start[a] = -1;
                    old_regs->end[a] = -1;
                }
            }
        }
        FREE_STATE(state);
        return match_end - pos;
    }
    case Cbol:
    {
        if (text == textstart || text[-1] == '\n')
            goto continue_matching;
        goto fail;
    }
    case Ceol:
    {
        if (text == textend || *text == '\n')
            goto continue_matching;
        goto fail;
    }
    case Cset:
    {
        NEXTCHAR(ch);
        if (code[ch/8] & (1<<(ch & 7)))
        {
            code += 256/8;
            goto continue_matching;
        }
        goto fail;
    }
    case Cexact:
    {
        NEXTCHAR(ch);
        if (ch != (unsigned char)*code++)
            goto fail;
        goto continue_matching;
    }
    case Canychar:
    {
        NEXTCHAR(ch);
        if (ch == '\n')
            goto fail;
        goto continue_matching;
    }
    case Cstart_memory:
    {
        reg = *code++;
        SET_REG_START(state, reg, text, goto error);
        goto continue_matching;
    }
    case Cend_memory:
    {
        reg = *code++;
        SET_REG_END(state, reg, text, goto error);
        goto continue_matching;
    }
    case Cmatch_memory:
    {
        reg = *code++;
        regstart = GET_REG_START(state, reg);
        regend = GET_REG_END(state, reg);
        if ((regstart == NULL) || (regend == NULL))
            goto fail;  /* or should we just match nothing? */
        regsize = regend - regstart;

        if (regsize > (textend - text))
            goto fail;
        if(translate)
        {
            for (; regstart < regend; regstart++, text++)
                if (translate[*regstart] != translate[*text])
                    goto fail;
        }
        else
            for (; regstart < regend; regstart++, text++)
                if (*regstart != *text)
                    goto fail;
        goto continue_matching;
    }
    case Cupdate_failure_jump:
    {
        UPDATE_FAILURE(state, text, goto error);
        /* fall to next case */
    }
    /* treat Cstar_jump just like Cjump if it hasn't been optimized */
    case Cstar_jump:
    case Cjump:
    {
        a = (unsigned char)*code++;
        a |= (unsigned char)*code++ << 8;
        code += (int)SHORT(a);
        if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
                PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cjump)");
            FREE_STATE(state);
                        return -2;
             }
        goto continue_matching;
    }
    case Cdummy_failure_jump:
    {
                unsigned char *failuredest;

        a = (unsigned char)*code++;
        a |= (unsigned char)*code++ << 8;
        a = (int)SHORT(a);
        assert(*code == Cfailure_jump);
        b = (unsigned char)code[1];
        b |= (unsigned char)code[2] << 8;
                failuredest = code + (int)SHORT(b) + 3;
        if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
                PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");
            FREE_STATE(state);
                        return -2;
        }
        PUSH_FAILURE(state, failuredest, NULL, goto error);
        code += a;
        if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
                PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)");
            FREE_STATE(state);
                        return -2;
             }
        goto continue_matching;
    }
    case Cfailure_jump:
    {
        a = (unsigned char)*code++;
        a |= (unsigned char)*code++ << 8;
        a = (int)SHORT(a);
        if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
                PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)");
            FREE_STATE(state);
                        return -2;
             }
        PUSH_FAILURE(state, code + a, text, goto error);
        goto continue_matching;
    }
    case Crepeat1:
    {
        unsigned char *pinst;
        a = (unsigned char)*code++;
        a |= (unsigned char)*code++ << 8;
        a = (int)SHORT(a);
        pinst = code + a;
        if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
                PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Crepeat1)");
            FREE_STATE(state);
                        return -2;
             }
        /* pinst is sole instruction in loop, and it matches a
         * single character.  Since Crepeat1 was originally a
         * Cupdate_failure_jump, we also know that backtracking
         * is useless: so long as the single-character
         * expression matches, it must be used.  Also, in the
         * case of +, we've already matched one character, so +
         * can't fail: nothing here can cause a failure.  */
        switch (*pinst++)
        {
        case Cset:
          {
                if (translate)
            {
                while (text < textend)
                {
                    ch = translate[(unsigned char)*text];
                    if (pinst[ch/8] & (1<<(ch & 7)))
                        text++;
                    else
                        break;
                }
            }
            else
            {
                while (text < textend)
                {
                    ch = (unsigned char)*text;
                    if (pinst[ch/8] & (1<<(ch & 7)))
                        text++;
                    else
                        break;
                }
            }
            break;
                }
        case Cexact:
        {
            ch = (unsigned char)*pinst;
            if (translate)
            {
                while (text < textend &&
                       translate[(unsigned char)*text] == ch)
                    text++;
            }
            else
            {
                while (text < textend && (unsigned char)*text == ch)
                    text++;
            }
            break;
        }
        case Canychar:
        {
            while (text < textend && (unsigned char)*text != '\n')
                text++;
            break;
        }
        case Csyntaxspec:
        {
            a = (unsigned char)*pinst;
            if (translate)
            {
                while (text < textend &&
                       (SYNTAX(translate[*text]) & a) )
                    text++;
            }
            else
            {
                while (text < textend && (SYNTAX(*text) & a) )
                    text++;
            }
            break;
        }
        case Cnotsyntaxspec:
        {
            a = (unsigned char)*pinst;
            if (translate)
            {
                while (text < textend &&
                       !(SYNTAX(translate[*text]) & a) )
                    text++;
            }
            else
            {
                while (text < textend && !(SYNTAX(*text) & a) )
                    text++;
            }
            break;
        }
        default:
        {
                FREE_STATE(state);
                PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
                return -2;
            /*NOTREACHED*/
        }
        }
        /* due to the funky way + and * are compiled, the top
         * failure- stack entry at this point is actually a
         * success entry -- update it & pop it */
        UPDATE_FAILURE(state, text, goto error);
        goto fail;      /* i.e., succeed <wink/sigh> */
    }
    case Cbegbuf:
    {
        if (text == textstart)
            goto continue_matching;
        goto fail;
    }
    case Cendbuf:
    {
        if (text == textend)
            goto continue_matching;
        goto fail;
    }
    case Cwordbeg:
    {
        if (text == textend)
            goto fail;
        if (!(SYNTAX(*text) & Sword))
            goto fail;
        if (text == textstart)
            goto continue_matching;
        if (!(SYNTAX(text[-1]) & Sword))
            goto continue_matching;
        goto fail;
    }
    case Cwordend:
    {
        if (text == textstart)
            goto fail;
        if (!(SYNTAX(text[-1]) & Sword))
            goto fail;
        if (text == textend)
            goto continue_matching;
        if (!(SYNTAX(*text) & Sword))
                goto continue_matching;
                goto fail;
    }
    case Cwordbound:
    {
        /* Note: as in gnu regexp, this also matches at the
         * beginning and end of buffer.  */

        if (text == textstart || text == textend)
            goto continue_matching;
        if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
            goto continue_matching;
        goto fail;
    }
    case Cnotwordbound:
    {
        /* Note: as in gnu regexp, this never matches at the
         * beginning and end of buffer.  */
        if (text == textstart || text == textend)
            goto fail;
        if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
                      goto continue_matching;
        goto fail;
    }
    case Csyntaxspec:
    {
        NEXTCHAR(ch);
        if (!(SYNTAX(ch) & (unsigned char)*code++))
            goto fail;
        goto continue_matching;
    }
    case Cnotsyntaxspec:
    {
        NEXTCHAR(ch);
        if (SYNTAX(ch) & (unsigned char)*code++)
            goto fail;
        goto continue_matching;
    }
    default:
    {
            FREE_STATE(state);
            PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");
        return -2;
        /*NOTREACHED*/
    }
    }



#if 0 /* This line is never reached --Guido */
    abort();
#endif
    /*
     *NOTREACHED
     */

    /* Using "break;" in the above switch statement is equivalent to "goto fail;" */
  fail:
    POP_FAILURE(state, code, text, goto done_matching, goto error);
    goto continue_matching;

  done_matching:
/*   if(translated != NULL) */
/*      free(translated); */
    FREE_STATE(state);
    return -1;

  error:
/*   if (translated != NULL) */
/*      free(translated); */
    FREE_STATE(state);
    return -2;
}


#undef PREFETCH
#undef NEXTCHAR

int re_search(bufp,
          string,
          size,
          pos,
          range,
          regs)
    regexp_t bufp;
    unsigned char *string;
    int size;
    int pos;
    int range;
    regexp_registers_t regs;
{
    unsigned char *fastmap;
    unsigned char *translate;
    unsigned char *text;
    unsigned char *partstart;
    unsigned char *partend;
    int dir;
    int ret;
    unsigned char anchor;

    assert(size >= 0 && pos >= 0);
    assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */

    fastmap = bufp->fastmap;
    translate = bufp->translate;
    if (fastmap && !bufp->fastmap_accurate) {
                re_compile_fastmap(bufp);
            if (PyErr_Occurred()) return -2;
    }

    anchor = bufp->anchor;
    if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
        fastmap = NULL;

    if (range < 0)
    {
        dir = -1;
        range = -range;
    }
    else
        dir = 1;

    if (anchor == 2) {
        if (pos != 0)
            return -1;
        else
            range = 0;
    }

    for (; range >= 0; range--, pos += dir)
    {
        if (fastmap)
        {
            if (dir == 1)
            { /* searching forwards */

                text = string + pos;
                partend = string + size;
                partstart = text;
                if (translate)
                    while (text != partend &&
                           !fastmap[(unsigned char) translate[(unsigned char)*text]])
                        text++;
                else
                    while (text != partend && !fastmap[(unsigned char)*text])
                        text++;
                pos += text - partstart;
                range -= text - partstart;
                if (pos == size && bufp->can_be_null == 0)
                    return -1;
            }
            else
            { /* searching backwards */
                text = string + pos;
                partstart = string + pos - range;
                partend = text;
                if (translate)
                    while (text != partstart &&
                           !fastmap[(unsigned char)
                               translate[(unsigned char)*text]])
                        text--;
                else
                    while (text != partstart &&
                           !fastmap[(unsigned char)*text])
                        text--;
                pos -= partend - text;
                range -= partend - text;
            }
        }
        if (anchor == 1)
        { /* anchored to begline */
            if (pos > 0 && (string[pos - 1] != '\n'))
                continue;
        }
        assert(pos >= 0 && pos <= size);
        ret = re_match(bufp, string, size, pos, regs);
        if (ret >= 0)
            return pos;
        if (ret == -2)
            return -2;
    }
    return -1;
}

/*
** Local Variables:
** mode: c
** c-file-style: "python"
** End:
*/